Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3
Example 2:
Input: root = [1,null,2]
Output: 2
Constraints:
The number of nodes in the tree is in the range [0, 10^4].
-100 <= Node.val <= 100
My Solution
Since the maximum depth of the binary tree in this problem is defined as the number of nodes in the path from the root to it’s deepest leaf node, we can find this by just adding the current node to the maximum depth of the left and right subtrees. The base case is if the node is null, in which case we just return 0.
Time complexity would be O(n), where n is the number of nodes in the tree, since we traverse all the nodes once. Space complexity is O(1) since we use constant extra space.
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(1+maxDepth(root.left), 1+maxDepth(root.right));
}
}